Language/OS - Multiplatform Resource Library/LANGUAGE OS.iso/cpp_libs/varia/grammar2.lha/c++grammar2.0/grammar5/grammar5.txt

Text File | 1991-07-11 | 64KB | 1,446 lines

Copyright (C) 1989.1990, James  A.   Roskind,  All  rights  reserved.
Abstracting  with credit is permitted.  The contents of this file may
be reproduced electronically, or in printed  form,  IN  ITS  ENTIRETY
with  no  changes, providing that this copyright notice is intact and
applicable in the copy.  No other copying is  permitted  without  the
expressed written consent of the author.

FILENAME: GRAMMAR5.TXT
AUTHOR: Jim Roskind
        Independent Consultant
        516 Latania Palm Drive
        Indialantic FL 32903
        [phone]
        [e-mail]
        or ...!uunet!leafusa!jar


    A YACC-able C++ 2.1 GRAMMAR, AND THE RESULTING AMBIGUITIES
                                        (Release 2.0 Updated 7/11/91)

ABSTRACT

This paper describes ambiguous aspects of the C++ language  that  have
been  exposed by the construction of a YACC-able grammar for C++.  The
grammar is provided in  a  separate  file,  but  there  are  extensive
references  to  the  actual  grammar.   This  release  of  the grammar
includes the output from a  yacc  cross-reference  tool  that  I  have
written.   The  discussion  in  this file will make many references to
that verbose output (typically provided in a  file  called  y.output),
but  the  file  is only critical if you are trying to "check my work",
rather than read my results.  The  format  of  the  machine  generated
documentation provided in y.output is defined in autodoc5.txt.

This  release  of  the  grammar  provides  what  I believe is complete
support for nested types, at least syntactically.  It does not support
either templates, or exception handling,  as  the  discussion  of  the
syntax for these elements is not finalized.

Theoretical  Note  (skip  if you hate theory): My C++ grammar does not
make use of the %prec or %assoc features of YACC, and hence  conflicts
are  never  hidden within my grammar.  The wondrous result is that, to
the extent to which my grammar can be seen to span the syntax  of  the
language,  in  all places where YACC reports no conflicts, the grammar
is a totally unambiguous statement of  the  syntax  of  the  language.
This  result  is  remarkable  (I think), because the "general case" of
deciding whether a grammar is ambiguous or not, is equivalent to  (the
unsolvable) halting problem.

Although  this  paper is terse, and at least hastily formed, I believe
that its content is so significant to my results that  it  had  to  be
included.   I  am  sorry  that I do not have the time at this point to
better arrange its contents.




CONTENTS

    CONTENTS
        INTRODUCTION
        REVIEW: STANDARD LEXICAL ANALYSIS HACK: TYPEDEFname vs IDENTIFIER
        STATUS OF MY "DISAMBIGUATED" GRAMMAR
    SUMMARY OF CONFLICTS

    17 EASY CONFLICTS, WITH HAPPY ENDINGS
    1 SR CONFLICT WITH AN ALMOST HAPPY ENDING
        6 NOVEL CONFLICT THAT YIELD TO SEMANTIC DISAMBIGUATION
    1 CONFLICT THAT CONSTRAINTS SUPPORT THE RESOLUTION FOR

    THE TOUGH AMBIGUITIES: FUNCTION LIKE CASTS AND COMPANY (17 CONFLICTS)
        THE TOUGH AMBIGUITIES: FUNCTION LIKE CASTS AND COMPANY
    LALR-only CONFLICTS IN THE GRAMMAR
        SAMPLE RESOLUTIONS OF AMBIGUITIES BY MY C++ GRAMMAR
        DIFFICULT AMBIGUITIES FOR C++ 2.0 PARSER TO TRY
        COMMENTARY ON CURRENT C++ DISAMBIGUATING RULES
        SOURCE OF CONFLICTS IN C++ (MIXING TYPES AND EXPRESSIONS)
    FUNCTION LIKE CAST vs DECLARATION AMBIGUITIES
    FUNCTION LIKE CAST vs DECLARATION : THE TOUGH EXAMPLE:

    CONCLUSION

    APPENDIX A:
      PROPOSED GRAMMAR MODIFICATIONS (fixing '*', and '&' conflicts)

    APPENDIX B:
      CANONICAL DESCRIPTION OF CONFLICTS and STATES





INTRODUCTION

This paper is  intended  to  go  into  significant  detail  about  the
ambiguities  that I have seen in the C++ 2.1 language (proposed in the
"C++ Annotated Reference Manual", a.k.a. ARM, by Ellis and Stroustrup)
and exposed by attempting to develop a YACC compatible (i.e., LALR(1))
grammar.  I must point out that this is NOT meant as an attack on  the
language  or  the  originators  thereof,  but  rather an R&D effort to
disambiguate some details.  (I personally believe that Stroustrup  et.
al.  are doing a GREAT job).  I have the vague hope that the extensive
hacking  that  I have done with YACC on the C++ grammar has given me a
rather novel vantage point.  (I  have  expressed  my  observations  to
Bjarne  Stroustrup,  and in doing so verified that other folks had not
previously  identified  several  of  my  points).   In  light  of   my
activities,  this  paper  includes  a fair amount of philosophizing. I
hope that none of this paper assumes too greatly that I  have  insight
that  is  beyond  that  of  the  readers, and certainly no insults are
intended.

If you like investigating grammars directly (rather than reading  what
I  have  to say), I would strongly suggest you read the ANSI C grammar
before looking at the C++  grammar.   Additionally,  if  you  want  to
really  understand  the  grammar,  as  suggested  in autodoc5.txt, the
grammar cross-reference provided in y.output is also very helpful. The
C++ grammar  is  pretty  large,  and  you  can  expect  the  following
statistics if you have a similar YACC to that I am using:

Berkeley YACC (1.8  01/02/91)

103 terminals, 186 nonterminals
665 grammar rules, 1256 states
24 shift/reduce conflicts, 18 reduce/reduce conflicts.

Sadly,  many  standard  yacc implementations have static limits on the
grammars that they can handle.  If you  find  this  to  be  a  problem
(i.e.,  you  yacc  says  "too  many  states", and terminates), I would
suggest acquiring Berkeley yacc (which is free), or  bison  (which  is
mostly  free),  or  purchasing  a  commercial  yacc implementation.  A
simple port of these publicly available sources on  machines  with  16
bit  "int"s  (e.g.,  most  PCs)  will  also  be  unable to process the
grammar.  PCYACC (from Abraxas  Software)  and  ydb  (from  Bloomsbury
Software),  are examples of commercial products that run on the PC and
Sun respectively, that I know from experience can yacc these  grammars
(I currently have no financial affiliation with either vendor).


REVIEW: STANDARD LEXICAL ANALYSIS HACK: TYPEDEFname vs IDENTIFIER

This section is targeted at readers that are not familiar with parsing
C  with a context free grammar.  The reader should note that there are
two distinct forms of `identifiers' gathered during lexical  analysis,
and  identified  as  terminal  tokens  in  both  of  my grammars.  The
terminal tokens are called IDENTIFIER  and  TYPEDEFname  respectively.
This  distinction  is  a  required  by  a fundamental element of the C
language.  The definition of a "TYPEDEFname" is a  lexeme  that  looks
like  a  standard  identifier,  but is currently defined in the symbol
table as being declared a typedef (or class, struct, enum  tag)  name.
All  other  lexemes  that appear as identifiers (and are not keywords)
are tokenized as IDENTIFIERs.  The  remainder  of  this  section  will
review the motivation for this approach.

Consider the following sample code, which uses the C language:

        ...
        int main() { f (*a) [4] ; ...

Most  readers  will intuitively parse the above sequence as a function
call to "f", with an argument "*a",  the  return  value  of  which  is
(probably)  a  pointer,  and  hence  can  be  indexed by "4".  Such an
interpretation presumes that the prior context was something like:

        ...
        extern float *a;
        char * f(float);
        int main() { f (*a) [4] ; ...

However, if the prior context was **INSTEAD**:

        ...
        typedef int f;
        extern float a;
        int main() { f (*a) [4] ; ...

then the interpretation  of  the  code  is  entirely  different.   The
fragment  in  question  actually redeclares a local variable "a", such
that the type of "a" is "pointer to array of 4 int's"!  So we  see  in
this   example   that  the  statement  "f(*a)[4];"  cannot  be  parsed
independent of context.

The standard solution to the above ambiguity is to allow  the  lexical
analyzer to form different tokens based on contextual information. The
contextual information that is used is the answer to the question: "Is
a  given  identifier  defined as a typedef name (or class name) at the
current point in the parse"?  I will refer to this feedback loop (from
the parser that stores information in  a  symbol  table,  wherein  the
lexer extracts the information) as the "lex hack".  With this lex hack
in  place the code fragment "f(*a)[4];" would be provided by the lexer
as either:

        IDENTIFIER '(' '*' IDENTIFIER ')' '[' INTEGERconstant ']' ';'

or

        TYPEDEFname '(' '*' IDENTIFIER ')' '[' INTEGERconstant ']' ';'

The two case are very easy for a context free grammar to  distinguish,
and  the  ambiguity  vanishes.  Note that the fact that such a hack is
used (out of necessity) demonstrates that C  is  not  a  context  free
language,  but  the hack allows us to continue to use an LR(1) parser,
and a context free grammar.

Note that this hack is, of necessity, also made  use  of  in  the  C++
grammar,  but  no  additional  feedback  (a.k.a.:  hack)  is (at least
currently) required.  The interested reader should also note that this
feedback loop (re: updating the symbol table) must be  swift,  as  the
lexical  analyzer  cannot  proceed  very  far  without this contextual
information.  This constraint on the feedback time often prevents  the
parser  from  "deferring" actions, and hence increases the pressure on
the parser to rapidly disambiguate token sequences.



STATUS OF MY "DISAMBIGUATED" GRAMMAR

Several independent reviews,  which  provided  a  complete  front  end
lexical  analyzers,  and  parsed existing C++ code, have verified that
the grammars span of  the  C++  language  appears  complete.   I  have
neither   incorporated   parametric   types  (a.k.a.   templates)  nor
exception handling into the grammars at this point, as  they  continue
to be in a state of flux.

The  grammar does (I believe) support all the features provided in C++
2.1, including multiple inheritance and the  enhanced  operator  "new"
syntax (includes placement expression). I believe that, except for the
minor  change  involving  not  permitting parentheses around bit field
names during a declaration, my C++ grammar supports a superset  of  my
ANSI  C  grammar. Note that I haven't inline expanded all the rules in
the C grammar that were required for C++ disambiguation (re: deferring
reductions), and hence a `diff' of the two grammars will not provide a
trivial comparison.  The resulting major  advantage  of  this  grammar
over  every  other  current  C++  parser  (that  I know of) is that it
supports old style function definitions AS WELL AS  all  the  standard
C++.   (It is my personal belief that such support was dropped by many
compilers and translators in order to resolve the many syntax problems
that appear within C++.  I believe this  grammar  shows  that  such  a
decision was premature).

My  list  of shift-reduce and reduce-reduce conflicts is currently: 24
shift/reduce, 18 reduce/reduce conflicts reported.  I have  chosen  to
leave  so  many conflicts in the grammar because I hope to see changes
to the syntax that will remove them, rather than making changes to  my
grammar  that  will firmly accept and disambiguate them.  (Considering
the detailed analysis presented here,  such  changes  would  only  add
unnecessary complications to an already large grammar).


SUMMARY OF CONFLICTS

The  following  summarizes the conflicts based on a simple description
of the nature of the conflict:

8 SR caused by operator function name with trailing * or &
    states: 131, 138, 281, 282

8 SR caused by freestore              with trailing * or &
    states: 571, 572, 778, 779

1 SR caused by dangling else and my laziness
    state: 1100

1 SR caused by member declaration of sub-structure, with trailing :
    state: 64

6 RR caused by constructor declaration vs member declaration
    states: 1105, 1152, 1175

1 SR caused by explicit call to destructor, without explicit scope
    state: 536




3 RR caused by function-like cast vs typedef redeclaration ambiguity
    state: 738

3 RR caused by function-like cast vs identifier declaration ambiguity
    state: 739

3 RR caused by destructor declaration vs destructor call
    state: 740

3 RR caused by parened initializer vs  prototype/typename
    state: 758

5 SR caused by redundant parened TYPEDEFname redeclaration vs old style cast
    states: 395, 621, 1038, 1102, 1103



Of these conflicts, the ones that most C++ parser authors  are  mainly
concerned  with  the  17  listed  at  the end of the above list.  They
relate to function-like-cast vs  declaration,  and  redundant  parened
TYPEDEFname  redeclaration  vs  old  style  cast,  etc.  The following
sections breeze through the "easy" conflicts, and then talk at  length
about these tough ones.



17 EASY CONFLICTS, WITH HAPPY ENDINGS

The first group of 17 SR conflicts:

8 SR caused by operator function name with trailing * or &
    states: 131, 138, 281, 282
8 SR caused by freestore              with trailing * or &
    states: 571, 572, 778, 779
1 SR caused by dangling else and my laziness
    state: 1100

have  very simple resolutions.  If you are reading this, I assume that
you are already familiar with the  if-if-else  conflict  (it  is  also
analyzed in depth in the autodoc5.txt file).

The  8  conflicts based "freestore with trailing * or &" can be hinted
at by the example:

        a = new int * * object;

Is the above the same as:

        a = (new int) * (* T);
or:
        a = (new (int *)) * T;

As a resolution,  the  "longest  possible  type"  is  isolated  by  my
grammar.  The result is:

        a = (new (int * * )) ...

which  leads  to  a  syntax  error  in my example!  This resolution is
indeed what is quietly specified  for  C++  2.0  (and  implemented  in
cfront).  The critical statement and example in the C++ 2.0 Ref Man at
the end of section 5.3.3 makes this resolution clear.

The  8 conflicts involving "operator function names with trailing * or
&" are quite similar to what was just presented.  The critical fact is
that "operator typename"  is  allowed  in  the  grammar  to  define  a
function.  Whenever a function is provided, but NOT followed by a '(',
the  address  of  the  function  is  implicitly  taken and used in the
expression (see draft ANSI C standard for finer  details).   For  some
class T, the following MIGHT all be valid statements:

        operator T;
        operator T*;
        operator T**;

If  the  above  are valid, then the interpretation of the following is
ambiguous:

        operator T * * a;

The above might be interpreted as:

        (operator T) * (* a);
or
        (operator (T *)) * a;

The default LR rules parse the largest possible type, and lead to:

        (operator (T * * )) ...

which in our example leads to a syntax error.  Here again the "longest
possible type..." rule supports my grammar.  Note that  this  rule  is
actually  a  consequence  (in my opinion) of the cfront implementation
via a YACC grammar, and the default resolution of  conflicts  in  that
grammar.



1 SR CONFLICT WITH AN ALMOST HAPPY ENDING

1 SR caused by member declaration of sub-structure, with trailing :
    state: 64

Note that this conflict is different from the one isolated in the 6/90
version of this grammar, that pertained to ':'.

The conflict now takes place (as seen in the demonstrations section of
y.output) in variations of the following program prefix:

    class A { class B :

The  problem  is  that  "class B" can be a declaration specifier, much
like "int".  When a bit field is defined, then  "int  :"  provides  an
unnamed  bit  field  member  of  a  structure.   My grammar avoids the
reduction of "class B" to declaration specifier in this  context,  and
hence  disambiguates  in  favor  of  a nested class, with a derivation
list:

    class A { class B : Parent { ..... };};

Although this  looks  reasonable  today,  when  template  classes  are
introduced,  and  the  supplied  type may be "int", then a real syntax
problem  will  be  present   (hence,   the   almost   happy   ending).
Specifically,  one  can  image a parameterized type, which is given as
input (i.e., an argument) either "signed int", or "unsigned int",  and
then  this  type  might  be  used  as a declaration specifier in a bit
field.  When the type is referred to during  the  parameterized  class
elaboration,  the  reference *can* be made in the form "class T", even
though "T" is simply "signed int".

For now (until the template syntax is worked out), the  disambiguation
provided by this grammar will do very nicely.



6 NOVEL CONFLICTS THAT YIELD TO SEMANTIC DISAMBIGUATION

The  conflicts  that  are discussed in this section have been deferred
(by A LOT of work, and A LOT of inline expansion) to occur when a ';',
or a '{' is reached.  At  that  point,  semantic  information  in  the
tokens can safely be used to decide which of two cases are at hand.

The conflicts are referred to as:

    6 RR caused by constructor declaration vs member declaration
    states: 1105, 1152, 1175


occur during a class/struct elaboration.  Consider the following class
elaborations:

        typedef int T1, T2, T3  ;
        class GOO { int a;} ;
        class FOO {
                GOO    T1  ; // clearly a redefinition of T1
                FOO  ( T2 ); // clearly a constructor
                GOO  ( T3 ); // redefinition of T3
                };

Note  that  the  last  two entries in FOO's elaboration "FOO(T2);" and
"GOO(T3);" are  tokenized  IDENTICALLY,  but  must  have  dramatically
different  meanings.   When I first found this ambiguity I was hopeful
that I could extend the lex hack that distinguishes TYPEDEFnames  from
random  IDENTIFIERs,  and distinguish something like CURRENTCLASSname.
Unfortunately, the  potential  for  elaborations  within  elaborations
appears  to  make  such a hack unworkable.  In addition, once I got my
grammar to defer all such ambiguous cases until a ';' was seen, I felt
confident that the ambiguity was resolved (and the introduction of  an
additional "hack" was unnecessary).

Note  that  the  situations  are  identical  when a '{' is seen, as it
presents the start of the body of either a function, or a constructor,
and an identical decision must be made.


1 CONFLICT THAT CONSTRAINTS SUPPORT THE RESOLUTION FOR

With  this  new  grammar,  the  ability  to  make  explicit  calls  to
constructors is supported.  As pointed out in section 12.4 of the ARM,
the  implicit  use  of  the  "this"  pointer  to  refer  to a specific
destructor leads to an ambiguity with the unary "~" operation.   As  a
result, in situations where it is possible to parse a sentence so that
the "~" is the unary operator, it is done.  The conflict is shown as:

1 SR caused by explicit call to destructor, without explicit scope
    state: 536

Note that the reduction:

    complex_name : '~' TYPEDEFname

is  what  is  used  to develop a "name" that can be used to refer to a
destructor  explicitly.   The  decision  is  made  to  not  use   this
reduction,  in favor of "something else" (which results from a shift).
Since the only alternative to specifying a destructor is to  make  "~"
serve as a unary operator, we are assured that we support the standard
given in the ARM.  Note that this should probably be officially listed
as  a part of the syntax restrictions, but in any case, it is at least
a disambiguating constraint, and we are guaranteed to support it.



THE TOUGH AMBIGUITIES: FUNCTION LIKE CASTS AND COMPANY (17 CONFLICTS)

The  ambiguities  listed  in  this  section  pertain  to  attempts  to
distinguish                declaration/types-names                from
expression-statements/expressions.  For example:

    char *b ="external" ; // declare a variable to confuse us :-)
    main () {
        class S;
        S (*b)[5]; // redeclare "b" pointer to array of 5 S's ?
               // OR ELSE indirect through b; cast to S; index using 5 ?
        }

The above is what I  call  the  "declaration  vs  function  like  cast
ambiguity".   Awareness  about  this ambiguity in this context appears
fairly widespread among C++ parser authors.  The  ARM  makes  explicit
reference  to  this  problem in section 6.8 "Ambiguity Resolution".  I
believe the underlying philosophy provided by the Reference Manual  is
that  if a token stream can be interpreted by an ANSI C compiler to be
a declaration, then a C++ compiler should disambiguate in favor  of  a
declaration.  Unfortunately, section 6.8 goes on to say:

    "To  disambiguate,  the whole statement may have to be examined to
    determine if it is an expression-statement, or a declaration.  ...
    The disambiguation is purely syntactic; that is,  the  meaning  of
    the  names, beyond whether they are type-names or not, is not used
    in the disambiguation".

The  above  advice  only  forestalls  the  inevitable  ambiguity,  and
complicates  the  language  in  the process.  The examples that follow
will demonstrate the difficulties.

There are several other contexts where such  ambiguities  (typedef  vs
expression) arise:

        1) Where a statement is valid (as shown above).
        2) As the argument to sizeof()
        3) Following "new", with the C++ syntax allowing a placement
                expression
        4) Immediately following a left paren  in  an  expression  (it
                might be an old style cast, and hence a type name)
        5) Following  a  left paren, arguments to constructors can be
                confused with prototype type-names.
        6) Recursively in any of the above,  following  a  left  paren
                (what  follows might be argument expressions, or might
                be function prototype parameter typing)

Examples of simple versions of the sizeof context are:

        class T;
        sizeof ( T    ); // sizeof (type-name)
        sizeof ( T[5] ); // again a type name
        sizeof ( T(5) ); // sizeof (expression)
        sizeof ( T()  ); // semantic error: sizeof "function returning T"?
                        // OR ELSE sizeof result of function like cast

Examples  of  the  old  style  cast ambiguity context, which are still
ambiguous when the '(' after the 'T' has been seen:

        class T { /* put required declarations here */
                };
        a = (T(      5));  // function like cast of 5
        b = (T(      )) 0; // semantic error: cast of 0 to type "function
                        // returning T"

In constructors the following demonstrates the problems:

        class T;
        T (b)(int  d ); // same as "T b(int);", a function declaration
        T (d)(int (5)); // same as "T d(5);", an identifier declaration
        T (d)(int ( )); // ambiguous

The problem can appear recursively  in  the  following  examples.   By
"recursively"  I  mean  that an ambiguity in the left-context has made
the parser unsure of whether an "expression"  or  a  "type"  is  being
parsed,  and  the ambiguity is continued by the token sequence.  After
the parser can determine what this subsequence is, it will in turn  be
able to disambiguating what the prior tokens were.

Recursion on the statement/declaration context:

        class S;
        class T;
        S (*b)(T); // declare b "pointer to function taking T returning S"
        S (*c)(T dummy); // same declaration as for "b"
        int dummy;
        S (*d)(T (dummy)); // This T might be casting dummy

Recursion on the sizeof context is shown in the following examples. As
before, the examples include semantic errors.

        class T;
        class S;
        sizeof ( T(S dummy) ); // sizeof "function taking S returning T"
        int dummy;
        sizeof ( T(S (dummy)) ); // sizeof "function taking S returning T"
                // OR ELSE cast dummy to S, and then cast that to T, which
                        // is the same as "sizeof T;"


The  following are the list of conflicts that fall into the categories
listed above.  To see the complete details of each conflict state  see
the y.output file supplied with this grammar.


3 RR caused by function-like cast vs typedef redeclaration ambiguity
    state: 738

3 RR caused by function-like cast vs identifier declaration ambiguity
    state: 739

3 RR caused by destructor declaration vs destructor call
    state: 740

3 RR caused by parened initializer vs  prototype/typename
    state: 758

5 SR caused by redundant parened TYPEDEFname redeclaration vs old style cast
    states: 395, 621, 1038, 1102, 1103

In  each  case  the  conflicts are resolved in favor of a declaration.
Note  that  this  decision  is  made  when  the  "declarator"  *seems*
complete.  Typically this takes place when a character (such as a ')',
',', or '=') that terminates a declarator or abstractor declarator  is
seen.  At  such  a  point,  an  my LR(1) grammar makes the decision to
support a declaration/type-name assuming it is possible.   (The  added
complexity of the LALR-only conflicts discussed in the next section).

Note  that  this disambiguation (provided by my grammar) is *NOT* what
is suggested in the ARM.   The  ARM  suggests  what  some  folks  have
referred  to  as "advanced parsing techniques" be used to disambiguate
based on first "pre-parsing" arbitrarily far ahead.  This approach  is
actually  not  "advanced  parsing", rather it is a through back to the
days before parsing was understood, and exponential search  algorithms
were  proposed  as  "parsing techniques." Currently, cfront supports a
hacked partial look-ahead technique, that alternately  "disambiguates"
hard  examples  and  "core-dumps"  for  others.  To date, I know of no
implementation  that  actually   comes   near   matching   the   ARM's
specification,   and   I  suspect  that  attempts  to  implement  such
conformance will lead to many buggy compilers,  that  support  varying
degrees  of  compliance  with  such ad-hoc requests for parsing.  Only
time will tell whether  the  ANSI  C++  committee  will  support  this
unimplemented  disambiguation technique.  Most users of cfront *think*
that the ARM is implemented in cfront, and that cfront implements  the
ARM.   This  area  of ambiguity not only demonstrates cfront's lack of
compliance  with  the  ARM,  but  also   exemplifies   some   of   the
unimplemented technology that is proposed in the ARM.


LALR-only CONFLICTS IN THE GRAMMAR

As  can  be seen in the analysis of the grammar in y.output, there are
some  LALR-only  conflict  contexts  in  some  of  the   reduce/reduce
conflicts.   Since yacc disambiguates in favor of lower numbered rules
during  R/R  conflict,  most  of   these   LALR-only   conflicts   are
insignificant  (see  autodoc5.txt  for  discussion  of  this concept).
Specifically, when the left context *requires* unambiguously that that
a certain reduction take place, and the parser was going  to  do  that
reduction   anyway   (by  default),  then  the  LALR-only  problem  is
insignificant.  Based on the above reasoning, the LALR-only  conflicts
in the following states are insignificant:

    states: 738(mostly), 739, 740, 1105

The  states where there are real LALR-only conflicts with significance
are:

    state 738 on ',' and '='

    state 758 on ',' and '='

The significant subsets of the unambiguous left context trees  (copied
from the y.output file) are:


LALR-only conflict contexts leading to state 738 and lookahead symbol <','>
    Possible reductions rules include (61,73)
        type_qualifier_list_opt : (61)
        postfix_expression : TYPEDEFname '(' ')' (73)

--738+-1014--952+-837(73)    $start IDENTIFIER '{' ! CLCL TYPEDEFname '(' TYPEDEFname '(' ')'
     |          --835(73)    $start IDENTIFIER '{' TYPEDEFname ! '(' TYPEDEFname '(' ')'
     |
     --748(73)    $start IDENTIFIER '(' '(' TYPEDEFname ! '(' ')'


LALR-only conflict contexts leading to state 738 and lookahead symbol <'='>
    Possible reductions rules include (61,73)
        type_qualifier_list_opt : (61)
        postfix_expression : TYPEDEFname '(' ')' (73)

--738+-1014--952(73)    $start IDENTIFIER '{' TYPEDEFname '(' ! TYPEDEFname '(' ')'
     |
     --748(73)    $start IDENTIFIER '(' '(' TYPEDEFname ! '(' ')'


LALR-only conflict contexts leading to state 758 and lookahead symbol <','>
    Possible reductions rules include (61,74)
        type_qualifier_list_opt : (61)
        postfix_expression : global_or_scoped_typedefname '(' ')' (74)

--758--754(74)    $start IDENTIFIER '(' '(' ! CLCL TYPEDEFname '(' ')'


LALR-only conflict contexts leading to state 758 and lookahead symbol <'='>
    Possible reductions rules include (61,74)
        type_qualifier_list_opt : (61)
        postfix_expression : global_or_scoped_typedefname '(' ')' (74)

--758--754(74)    $start IDENTIFIER '(' '(' ! CLCL TYPEDEFname '(' ')'


As explained in the description of the "sample sentence" that is given
for  each  context  (see  autodoc5.txt),  it  is not unique, and it is
*especially* non-unique to the left of  the  '!'  symbol.   Never  the
less, it provides (most of the time) rapid insight into the conflicts,
which  makes  it  unnecessary to look at the details of the associated
demonstrations (also provided in the y.output file).

Looking at these examples, it  can  be  seen  that  in  each  case,  a
parenthesized  type  name  is  created,  and  a trailing ',' or '=' is
found.  Since the type-name used in an old style cast  cannot  contain
such  symbols  as  ',' or '=' (unprotected by parens), the presence of
such a token  precludes  the  possibility  of  the  sequence  being  a
typename.  For example, looking at the left context for state 738 that
includes state 952, consider the fragment:

    struct  TYPE1 { ...... } ;
    struct  TYPE2 { ...... } ;
    main(){
        TYPE1 ( ( TYPE2()


There  is  a chance that TYPE2 is about to be redeclared at this inner
scope.  In such a case the fragment might continue:


    struct  TYPE1 { ...... } ;
    struct  TYPE2 { ...... } ;
    main(){
        TYPE1 ( ( TYPE2()));
        }

with lots of redundant parents around the redeclared "TYPE2".   As  an
alternative, the fragment might continue:

    struct  TYPE1 { ...... } ;
    struct  TYPE2 { ...... } ;
    main(){
        TYPE1 ( ( TYPE2() + 10));

and  become an expression.  The problematic situation is provided when
(for example) a ',' follows:

    struct  TYPE1 { ...... } ;
    struct  TYPE2 { ...... } ;
    main(){
        TYPE1 ( ( TYPE2() ,

Clearly, as provided in the analysis, this must be a case  where  only
an  expression  can  result,  as a ',' could not be placed as shown if
TYPE2 were being redeclared.

Careful consideration of each of the other LALR-only conflicts reveals
an identical fundamental problem.

As is the basis for all  LALR-only  contexts,  there  are  some  other
contexts  where this same LALR states 738 is used with a trailing ',',
and it is possible for the item to  the  left  of  the  ','  to  be  a
declarator  (specifically,  when the declarator is the first type in a
prototype list, a comma may follow it).  Interestingly,  this  precise
problem  is also the reason for the '=' look-ahead problem, as '=' may
be used to specify an initializer in a prototype list, but  can  never
be  found  in  an abstract declarator (as is required for an old style
cast typename), or  adjacent  to  a  simple  declaration's  declarator
*while* nested within parenthesis.

With  this  insight, it is not difficult to change the grammar so that
the critical rules are repeated for these two distinct contexts.  As I
mentioned in my autodoc5.txt file,  I  am  working  on  a  subtle  and
automated  method  for  removing  these  LALR-only conflicts.  I would
prefer (for now) to leave these conflicts in place and remove them via
subtle  means,  rather  than  by  brute   replications   of   critical
reductions.   Since  the nesting complexities of these scenarios seems
large (re: function like cast of function like cast  etc.),  I  expect
that  leaving  these  conflicts  in  the  grammar will have no adverse
effects on users with real code.   Recall  that  the  worst  that  can
happen  with  such  conflicts  remaining  is that an expression can be
signaled as a syntax error, when in fact it is "unambiguous", based on
one token of look-ahead.


SAMPLE RESOLUTIONS OF AMBIGUITIES BY MY C++ GRAMMAR

Since my grammar tends to disambiguate "prematurely" (i.e., the parser
does not use infinite lookahead) when compared with the ARM  standard,
it tends to force non-declarations into being declarations.  Later on,
when   the   tokens  appear  that  require  an  interpretation  as  an
expression, a syntax error results.  Hence, the  "hard  examples"  are
those   in   which  the  disambiguating  tokens  appear  late  in  the
expressions.

Of the "hard examples" given in the ARM (r6.8), my  grammar  can  only
"properly" detect a "statement-expression" for the stream:

        T(a,5)>>c;

All  the  other  examples  default  to  a declarator after the closing
parenthesis  following  the  identifier.   (See  my  comments  in  the
conclusion section of this paper).

I  actually  am  not sure I agree with all the examples in the C++ 2.0
Reference Manual. Specifically, the example in section 6.8:

        T (*d) (double(3));  // expression statement

In the example "T"  is  specified  to  be  a  simple-type-name,  which
includes  all  the  basic  types  as  well  as  class-names, and more.
Considering the following are valid declarations:

        void *a (0);
        void *b (int(0));
        void (*c)(int(0));

I am unable to see the "syntactic" difference between this last  token
stream  and  the  example  just  cited  in  the  reference manual.  My
simplistic parser gives me the result that  I  at  least  expect.   It
concludes  (prematurely, but seemingly correctly) that the stream is a
declaration (with a new style initializer).

As a positive note, my grammar is able to parse the  example  given  a
while back in comp.lang.c++, that Zortech C++ 1.07 could not parse:

        a = (double(a)/double(b))...;

Apparently,   upon   seeing   "(double"   some  parsers  commit  to  a
parenthesized type-name for a cast expression, and cannot  proceed  to
parse  a  parenthesized  expression.   No  mention  of this problem is
listed in my conflict list, as resolution of this problem is simply  a
matter of letting the LR parser wait long enough before committing. My
grammar commits when it sees "a" in "(a)" to providing an expression.


DIFFICULT AMBIGUITIES FOR A "C++ 2.0" COMPATIBLE PARSER TO TRY

Having seen the above contexts, I would be curious to see if other C++
front  ends  with  "smart  lexers"  (such  as  cfront)  can handle the
following.   These  examples  are  not  guaranteed  to  be   evaluated
correctly  by  my grammar, but I expect them to demonstrate weaknesses
in many other parsers.  The interpretation of these examples  per  C++
2.0 definitions requires massive lookahead.  In addition, the examples
are  generally unreadable by humans, and rarely parsed the same way by
any two implementations.

    main()
      {
      class T
        {
        /* ... */
        } a;
      typedef T T1,T2,T3,T4,T5,T7,T8,T9,Ta,Tb,Tc,Td;
        { /* start inner scope */
        T((T1)         ); // declaration
        T((T2)    a    ); // Statement expression
        T((T3)(       )); // declaration of T3
        T((T4)(T      )); // declaration of T4
        T((T5)(T  a   )); // declaration of T5
        T((T6)(T((a) ))); // declaration of T6
        T((T7)(T((T) ))); // declaration of T7
        T((T8)(T((T)b))); // statement expression

        T(b[5]); // declaration
        T(c());  // declaration
        T(d()[5]);  // statement expression ? (function returning array
                      // is semantically illegal, but syntactically proper)
        T(e[5]());  // statement expression ? (No array of functions)
        T(f)[5]();  // statement expression ?  "                   "

        T(*Ta() )[5] [4];  //declaration
        T(*Tb() [5]) [4];  //statement expression ? (function returning array)

        T(*Tc()) [3 +2];  //declaration
        T(*Td()) [3 ]+2;  //statement expression

        }
      }


COMMENTARY ON C++ 2.0 DISAMBIGUATING RULES

There are two distinct thrusts in conflict disambiguation as  provided
by  AT&T's  efforts to define a standard for C++.  The first thrust is
"parse tokens into the longest possible declarator, and  identify  the
syntax  errors  that  result".   The  second thrust is to "use massive
external technology ("smart lexer", a.k.a.: "recursive  decent  parser
that  helps  the  lexer",  a.k.a.   LALEX)  to look ahead, so that the
parser doesn't mis-parse a function-like-cast  as  a  declaration  and
induce  a  syntax  error".   The  first  is  a commitment to LR parser
technology, and an existing grammar (which could be cleaned up).   The
second  is  a commitment to NOT use an LR parser, and to the use of an
existing implementation.

It is my belief that LR parsers are well understood, and the  addition
of a "smart lexer" destroys all structure in a parser.  The result can
be anticipated to become a quagmire of code and hacks.  With this firm
conviction,  I  have  provided my grammar in the hopes that a standard
can emerge that IS well defined, and is implementable, and is readable
by humans.


SOURCE OF CONFLICTS IN C++ (MIXING TYPES AND EXPRESSIONS)

One fundamental strength in C is the similarity  between  declarations
and  expressions.   The  syntax  of  the  two  is  intended to be very
similar, and the result is a clean declaration and expression  syntax.
(It  takes  some  getting  used  to,  but  it  is in my opinion good).
Unfortunately, there are some slight distinctions  between  types  and
expressions,  which  Ritchie  et.  al.  apparently noticed.  It is for
this reason (I am guessing) that the C cast operator REQUIRES that the
type be enclosed in parenthesis.  Moreover,  there  is  also  a  clear
separator in a declaration between the declarator and the initializing
expression  (the  '=') (as some of you know, there is some interesting
history  in  this  area.).   The  bottom  line  (as  seen  with  20-20
hindsight)  is:  "keep  declarations  and expressions separate".  Each
violation of this basic rule has induced conflicts.


To be concrete about the differences between  types  and  expressions,
the following two distinctions are apparent:

    1)  Abstract declarators are permitted.  No analogy is provided in
    expressions.  The notable distinction is that abstract declarators
    include the possibility of trailing '*' tokens.

    2) The binding of elements in a declaration is very different from
    any expression.  Notably,  the  declaration-specifiers  are  bound
    separately  to  each  declarator  in  the  comma separated list of
    declarators (example:  int  a,  b,  c;).   With  (most  forms  of)
    expressions,   a   comma   provides   a  major  isolation  between
    expressions.

C also used  reserved  names  to  GREATLY  reduce  the  complexity  of
parsing.   The  introduction of typedef names increased the complexity
(it made the language context sensitive), but a  simple  hack  between
lex and YACC overcame the problem.  An example is the statement:

        name (*b)[4];

Note  that  this  is  ambiguous,  EVEN  in  ANSI  C,  IF  there  is no
distinction between type-names and function names!  (i.e.,  "b"  could
be getting redeclared to be of type "pointer to array of name", OR the
function  "name"  could  be  called  with argument "*b", the result of
which is indexed to the 4th element). In C, the  two  kinds  of  names
(TYPEDEFnames and function names (a.k.a.: declared identifiers)) share
a  name  space,  and  at  every  point  in a source program the (hack)
contextual distinction can be made by the tokenizer.  Hacks  are  neat
things in that the less you use them, the more likely they are to work
when you REALLY need them (i.e., you don't have to fight with existing
hacks).   Having  worked on designing and implementing a C compiler, I
was pleasantly amazed at how the constructs all fell together.

The major violations of this approach (i.e., keep declaration separate
from expressions) that come to mind with C++ are:

        function-like-casts,
        freestore expressions without parens around the type,
        conversion function names using arbitrary type specifiers,
        parenthesized initializers that drive constructors.

The last problem, parenthesized initializers, provides  two  areas  of
conflicts.  The first is really an interference issue with old style C
function  definitions,  which  only bothers folks at file scope (GNU's
G++ compiler considered this to be too great  an  obstacle,  and  they
don't currently support old style C definitions!).  The second part of
this   conflict   involves   a  more  subtle  separation  between  the
declarator, and the initializer. (K&R  eventually  provided  an  equal
sign  as  an unequivocal separator, but parens used in C++ are already
TOO overloaded to separate anything).  The significance of  this  lack
of  a  clear  separator  is  that  it  is difficult to decide that the
"declarator" is complete, and that the declared name should  be  added
to  the scope.  The last problem does interact in a nasty way with the
function-like cast vs declaration conflicts  (the  problem  slows  the
feedback  loop  to  the  symbol  table, which is critical to continued
lexing).  The parened initializers also provide another context  where
it  is  difficult  to distinguish between expressions (a true argument
list for the constructor) and a declaration continuation (a  parameter
type list).

The  second  problem  listed falls out of the "new-expression" with an
unparenthesized type.  This form of freestore (such as "new int *  *")
allows  types  to  be placed adjacent to expressions, and the trailing
'*' ambiguity rears its head.  I can easily prove  that  this  is  the
culprit  in  terms  of  specific  ambiguities,  in that removing these
(unnecessary?) forms significantly disambiguates the grammar.  (It  is
rather  nice  to  use  YACC  as  a  tool  to  prove  that a grammar is
unambiguous!).  It is interesting to note that if only the  derivation
of  a  freestore  expression  were  limited to (using the non-terminal
names of the form that the C++ Reference manual uses):

        new placement-opt ( type-name )  parened-arg-list-opt

then all the LR(1)  reduce  conflicts  based  on  this  problem  would
vanish.  Indeed, the culprit can clearly be shown to be:

        new placement-opt  restricted-type-name parened-arg-list-opt

The  characters  which  excite  these reduction conflicts are '*', and
'&'.

The    third    problem    that    I    indicated     involves     the
conversion-function-name.   Here  again, if the syntax were restricted
to ONLY:

        operator simple-type-name

then the LR(1) conflicts would vanish.  It is interesting to note that
the  keyword  "operator"  serves  as  the  left  separator,  and   the
restriction   to  "simple-type-name"  results  in  an  implicit  right
separator  (simple-type-names  are  exactly  one  token  long).    The
conflicts  appear  when  multiple tokens are allowed for a declaration
specifier, and an optional pointer-modifier list may  be  added  as  a
postfix.   The  conflicts  that  result  from  this lack of separation
include all those provided by the freestore example.

Here again (as with the unambiguous version of freestore)  the  syntax
could be extended to:

operator_function_name :
        OPERATOR any_operator
        | OPERATOR basic_type_name
        | OPERATOR TYPEDEFname
        | OPERATOR type_qualifier
        | OPERATOR '(' type_name ')'
        ;

instead of:

operator_function_name :
        OPERATOR any_operator
        | OPERATOR type_qualifier_list            operator_function_ptr_opt
        | OPERATOR non_elaborating_type_specifier operator_function_ptr_opt
        ;

and  the  ambiguities  would vanish (and the expressivity would not be
diminished).


FUNCTION LIKE CAST vs DECLARATION AMBIGUITIES

The real big culprit (i.e., my anti-favorite) in this whole  ambiguity
set   (re:   keeping   types   and   expressions   separate)   is  the
function-like-cast.  The reason why it is so  significant  (to  an  LR
parser)   is  that  the  binding  of  a  type-name,  when  used  in  a
function-like-cast,  is  directly  to  the   following   parenthesized
argument list.  In contrast, the binding of a type-name when used in a
declaration  is to all the "stuff" that follows, up until a declarator
termination mark like a ',', ';' or '='. Life really gets tough for LR
folks when the parse stack MUST be reduced, but the parser just  can't
tell  how  yet.  With this problem, the hacks began to appear (re: the
"smart lexer").  Note that these new style casts are much more than  a
notational  convenience  in  C++.   The necessity of the function like
cast lies in the fact that such a cast  can  take  several  arguments,
whereas the old style cast is ALWAYS a unary operator.

I was (past tense) actually working towards resolving this problem via
some  standard  methods that I have developed (re: inline expansion of
rules to provide deferred reduction).  I was (past tense)  also  using
one  more  sneaky  piece  of  work  to  defer the reductions, as I was
carefully making use of right recursion (instead of the standard  left
recursion)  in  order  to  give  the  parser a chance to build up more
context.  I can demonstrate the usefulness of right recursive grammars
in disambiguating difficult toy grammars.  Unfortunately,  I  realized
at  some  point  that I NEEDED to perform certain actions (such as add
identifiers to the symbol table) in order  to  complete  the  parse!?!
This  was  my catch 22.  I could POSSIBLY parse using an LALR grammar,
if  I  could  only  defer  actions  until  I  had  enough  context  to
disambiguate.   Unfortunately,  I  HAD to perform certain actions (re:
modify the symbol table, which changed the action  of  the  tokenizer)
BEFORE  I  could  continue to examine tokens!  In some terrible sense,
the typedef hack had come back to haunt me.

I backed off a bit in my grammar after reaching this wall, and now  my
grammar  only  waits  until  it reaches the identifier in the would be
declarator.  I really  didn't  want  to  parse  the  stuff  after  the
identifier  name  (sour  grapes?),  because  I  knew  I would not (for
example) be able to identify  a  "constant  expression"  in  an  array
subscript  (most of the time, if it isn't constant, then it can't be a
declaration).  I don't believe that a compiler  should  compete  in  a
battle  of  wits  with  the  programmer,  and  the  parser was already
beginning to outwit me (i.e., I was having a hard time  parsing  stuff
mentally that is provided as examples in the 2.0 Reference Manual.  In
fact, many reviewers as well as the author had difficulty, and that is
why errors appeared there originally, as well as in the ARM).


FUNCTION LIKE CAST vs DECLARATION : THE TOUGH EXAMPLE:

The  following  is about the nastiest example that I have been able to
construct for this ambiguity group.  I am presenting it here  just  in
case someone is left with a thought that there is "an easy way out".

The   fact  that  identifiers  can  remain  ambiguous  SO  LONG  after
encountering them can cause no end of  trouble  to  the  parser.   The
following  example  does  not  succumb to static (re: no change to the
symbol table)  anticipatory  lexing  of  a  statement.   As  such,  it
demonstrates  the  futility  of  attempting  to use a "smart lexer" to
support the philosophy: "If it can be interpreted  as  a  declaration,
then so be it; otherwise it is an expression".  This ambiguous example
exploits  the  fact that declarators MUST be added to the symbol table
as  soon  as  they  are  complete  (and  hence  they   mask   external
declarations).

First I will present the example without comments:

class Type1 {
            Type1 operator()(int);
            } ;
class wasType2 { ...};
int (*c2)(Type1 dummy);

main ()
    {
    const int    a1  = 0, new_var  (4), (*c1)(int     (a1));
    Type1       (a2) = 3, wasType2 (4), (*c2)(wasType2(a1));
    }




Now to repeat the example with comments:

class Type1 {....
            Type1 operator()(int);
            } ;
class wasType2 { ....}; /* we will almost redeclare this typename!?! */
int (*c2)(Type1 dummy); /* we will NOT redeclare Type1 */

main ()
    {
    /* The first line is indeed simple.  It is simply placed here
    to hint at how the second line MIGHT analogously be parsed. */

    const int    a1  = 0, new_var  (4), (*c1)(int     (a1));

    /*  As  a review, "a1" is declared to be a constant with value 0.
        "new_var" is declared to be another constant, but with  value
        4.  Finally,  "c1"  is  declared  to  be a pointer to a const
        integer, and the initial value of this pointer is  "int(a1)",
        which  is  the  same  as "int(0)", or simply "0" (a.k.a., the
        null pointer). It is significant that "a1" entered the symbol
        table  quickly  so  that  it  could  be  used  later  in  the
        declaration. */

    /* Static lexing of what follows will suggest that the  following
    is  also  a  declaration.   This  statement  is  actually 3 comma
    separated expressions!! The explanation that follows  shows  that
    assuming   the   2nd  statement  is  a  declaration  leads  to  a
    contradiction. */

    Type1      (a2) = 3, wasType2 (4), (*c2)(wasType2(a1));

    /* Assume this second statement is a declaration.  Note  that  by
    the  time  "c2" is parsed, "wasType2" has been redeclared to be a
    variable of type "Type1".  Hence  "wasType2(a1)"  is  actually  a
    function  call  to  "wasType2.operator()(a1)",  and  it  is not a
    function    prototype    arg    list.     It     follows     that
    "(*c2)(wasType2(a1))"  is  an  expression,  and NOT a declarator!
    Since this last entry is not a declarator, the  entire  statement
    must  be an expression (ugh! it is time to backtrack). After much
    work on my part, I think it might even be  a  semantically  valid
    expression.   Once this backtracking is complete, we see that the
    first expression "Type1 (a2) = 3" is  an  assignment  to  a  cast
    expression.  The second expression "wasType2 (4)", is a cast of a
    constant.  The  third  expression  "(*c2)(wasType2(a1))",  is  an
    indirect  function  call.  The argument of the call is the result
    of a cast.  Note that "wasType2" is  actually  never  redeclared,
    but it was close! */

    /*  For  those of you who can parse this stuff in your sleep, and
    noticed the slight error  in  the  above  argument,  I  have  the
    following "fix".  The error is that the

        "(*c2)(wasType2(a1))"

    could actually be a declaration with a parenthesized initializer.
    I could have changed this token subsequence to:

        "(*(*c2)(wasType2(a1)))(int(a1))"

    and avoid the constructor ambiguity, but it would only complicate
    the  discussion.   Note that in this form, if "wasType2" is not a
    type, the the quoted text cannot be a declaration.*/

    /* Two parens are all a user would need to  add  to  the  cryptic
    example  to  unambiguously  specify  that  this  statement  is an
    expression.  Specifically: */

       (Type1) (a2) = 3, wasType2 (4), (*c2)(wasType2(a1));
    /* or ...*/
       (Type1 (a2) = 3), wasType2 (4), (*c2)(wasType2(a1));

    /* I would vote for a syntax error in such ambiguous stream, with
    an  early  decision that it was a declaration.  After seeing this
    example, I doubt that I could quickly assert that I could produce
    a non-backtracking parser that disambiguates statements according
    to the C++ 2.0 rule.  I am sure  I  can  forget  about  a  simple
    lex-YACC combination doing it. */

    }


Most  simply  put,  if  a  "smart  lexer"  understands  these: a) I am
impressed, b) Why use a parser when a lexer can parse so well?

The bottom line is that disambiguation of declarations via "If it  can
be  a  declaration,  then  it is one", seems to require a backtracking
parser. (Or some very fancy parsing approach).  I am not even sure  if
the above examples are as bad as it can get!


CONCLUSION

I believe that the C++ grammar that I have made available represents a
viable machine readable standard for the syntax description of the C++
language.   In  cases  where  the  ambiguities  are  still  exposed by
conflicts (as noted by YACC), to further  defer  resolution  would  be
detrimental  to  a  user.   I  see no benefit in describing a computer
language that must support human writers, but cannot be understood  by
humans.    Any   code   that  exploits  such  deferral  is  inherently
non-portable, and deserves to be diagnosed as  an  error  (my  grammar
asserts a "syntax error").  Rather than dragging the C++ language into
support  for  a ad-hoc parser implementations such as what cfront (and
the "smart lexer") have tried unsuccessfully  to  implement,  I  would
heavily  suggest  the  use  of  my  grammar.  I do not believe that my
grammar would "break" much existing code, but in cases where it would,
the code would not be portable anyway (other than  to  a  port  of  an
IDENTICAL parser).

I  hope  to see a great deal of use of my grammars, and I believe that
standardizing on the represented syntax will unify  the  C++  language
greatly.

        Jim Roskind
        Independent Consultant
        516 Latania Palm Drive
        Indialantic FL 32903
        [phone]
        [e-mail] or ...uunet!leafusa!jar



APPENDIX A:
  PROPOSED GRAMMAR MODIFICATIONS (fixing '*', and '&' conflicts)

Based  on  the  other  items  described  above,  I  have the following
suggestions for cleaning up the grammar definition.  Unfortunately, it
provides subtle variations from the "C++ 2.0" standard.


Current Grammar:

operator_function_name :
        OPERATOR any_operator
        | OPERATOR type_qualifier_list            operator_function_ptr_opt
        | OPERATOR non_elaborating_type_specifier operator_function_ptr_opt
        ;


operator_new_type:
        type_qualifier_list              operator_new_declarator_opt
                        operator_new_initializer_opt

        | non_elaborating_type_specifier operator_new_declarator_opt
                        operator_new_initializer_opt
        ;

Proposed new grammar (which requires parens around complex types):

operator_function_name :
        OPERATOR any_operator
        | OPERATOR basic_type_name
        | OPERATOR TYPEDEFname
        | OPERATOR type_qualifier
        | OPERATOR '(' type_name ')'
        ;

operator_new_type:
        basic_type_name    operator_new_initializer_opt
        | TYPEDEFname      operator_new_initializer_opt
        | type_qualifier   operator_new_initializer_opt
        | '(' type_name ') operator_new_initializer_opt
        ;

The impact of the above changes is that all complex type names  (i.e.:
names  that are not simply a typedef/class name, or a basic type names
like char) must be enclosed in  parenthesis  in  both  `new  ...'  and
`operator ...' expressions. Both of the above changes would clear up a
number  of  ambiguities.   In some sense, the current "disambiguation"
(of trailing '*', and '&') is really  a  statement  that  whatever  an
LR(1)  parser cannot disambiguate is a syntax error.  In contrast, the
above rules define an unambiguous grammar.



APPENDIX B:
    CANONICAL DESCRIPTION OF CONFLICTS and STATES


The following  is  directly  extracted  from  the  canonical  list  of
conflicts  provided  in  the  y.output  file.   For  a  more  complete
discussion of the significance of the canonical sentence provided with
each state, see the autodoc5.txt file.  I have also  added  annotation
to connect these sentence to the summary given earlier:

state 64: STRUCT IDENTIFIER  .  ':'    (1 reduction, or a shift)
    1 SR caused by member declaration of sub-structure, with trailing :

state 131: OPERATOR INT  .  '*'    (1 reduction, or a shift)
    8 SR caused by operator function name with trailing * or &

state 131: OPERATOR INT  .  '&'    (1 reduction, or a shift)
    8 SR caused by operator function name with trailing * or &

state 138: OPERATOR CONST  .  '*'    (1 reduction, or a shift)
    8 SR caused by operator function name with trailing * or &

state 138: OPERATOR CONST  .  '&'    (1 reduction, or a shift)
    8 SR caused by operator function name with trailing * or &

state 281: OPERATOR INT '*' CONST  .  '*'    (1 reduction, or a shift)
    8 SR caused by operator function name with trailing * or &

state 281: OPERATOR INT '*' CONST  .  '&'    (1 reduction, or a shift)
    8 SR caused by operator function name with trailing * or &

state 282: OPERATOR INT '*'  .  '*'    (1 reduction, or a shift)
    8 SR caused by operator function name with trailing * or &

state 282: OPERATOR INT '*'  .  '&'    (1 reduction, or a shift)
    8 SR caused by operator function name with trailing * or &

state 395: CLCL TYPEDEFname '(' TYPEDEFname  .  ')'    (1 reduction, or a shift)
    5 SR caused by redundant parened TYPEDEFname redeclaration vs old style cast
    Make declaration rather than expression.

    problem: Constructor with anonymous arg name at file scope
        looks like redeclaration of typename.

        A::B(C){}  should be the same as  A::B(C x){}
        (but it isn't for an LR(1) grammar)

state 536: IDENTIFIER '(' '~' TYPEDEFname  .  '('    (1 reduction, or a shift)
    1 SR caused by explicit call to destructor, without explicit scope

state 571: IDENTIFIER '(' NEW INT  .  '*'    (1 reduction, or a shift)
    8 SR caused by freestore              with trailing * or &

state 571: IDENTIFIER '(' NEW INT  .  '&'    (1 reduction, or a shift)
    8 SR caused by freestore              with trailing * or &

state 572: IDENTIFIER '(' NEW CONST  .  '*'    (1 reduction, or a shift)
    8 SR caused by freestore              with trailing * or &

state 572: IDENTIFIER '(' NEW CONST  .  '&'    (1 reduction, or a shift)
    8 SR caused by freestore              with trailing * or &

state 621: CLCL TYPEDEFname '(' TYPEDEFname '[' ']'  .  ')'    (1 reduction, or a shift)
    5 SR caused by redundant parened TYPEDEFname redeclaration vs old style cast
    Make declaration rather than expression.
    Don't form an old style cast.

state 738: IDENTIFIER '(' TYPEDEFname '(' ')'  .  ')'    (2 reductions)
    3 RR caused by function-like cast vs typedef redeclaration ambiguity
    LALR-only can be ignored.
    Make declaration rather than expression.

state 738: IDENTIFIER '(' TYPEDEFname '(' ')'  .  ','    (2 reductions)
    3 RR caused by function-like cast vs typedef redeclaration ambiguity
    Problem with LALR-only conflict.
    Make declaration rather than expression.

state 738: IDENTIFIER '(' TYPEDEFname '(' ')'  .  '='    (2 reductions)
    3 RR caused by function-like cast vs typedef redeclaration ambiguity
    Problem with LALR-only conflict.
    Make declaration rather than expression.

state 739: IDENTIFIER '(' TYPEDEFname '(' IDENTIFIER  .  '('    (2 reductions)
    3 RR caused by function-like cast vs identifier declaration ambiguity
    Make declaration rather than expression.

state 739: IDENTIFIER '(' TYPEDEFname '(' IDENTIFIER  .  ')'    (2 reductions)
    3 RR caused by function-like cast vs identifier declaration ambiguity
    LALR-only can be ignored.
    Make declaration rather than expression.

state 739: IDENTIFIER '(' TYPEDEFname '(' IDENTIFIER  .  '['    (2 reductions)
    3 RR caused by function-like cast vs identifier declaration ambiguity
    Make declaration rather than expression.

state 740: IDENTIFIER '(' TYPEDEFname '(' '~' TYPEDEFname  .  '('    (2 reductions)
    3 RR caused by destructor declaration vs destructor call
    Make declaration of destructor rather than expression.

state 740: IDENTIFIER '(' TYPEDEFname '(' '~' TYPEDEFname  .  ')'    (2 reductions)
    3 RR caused by destructor declaration vs destructor call
    LALR-only can be ignored.
    Make declaration of destructor rather than expression.

state 740: IDENTIFIER '(' TYPEDEFname '(' '~' TYPEDEFname  .  '['    (2 reductions)
    3 RR caused by destructor declaration vs destructor call
    Make declaration of destructor rather than expression.

state 758: IDENTIFIER '(' CLCL TYPEDEFname '(' ')'  .  ')'    (2 reductions)
    3 RR caused by parened initializer vs prototype/typename
    Make declaration rather than expression.

state 758: IDENTIFIER '(' CLCL TYPEDEFname '(' ')'  .  ','    (2 reductions)
    3 RR caused by parened initializer vs prototype/typename
    Problem with LALR-only conflict.
    Make declaration rather than expression.

state 758: IDENTIFIER '(' CLCL TYPEDEFname '(' ')'  .  '='    (2 reductions)
    3 RR caused by parened initializer vs prototype/typename
    Problem with LALR-only conflict.
    Make declaration rather than expression.

state 778: IDENTIFIER '(' NEW INT '*' CONST  .  '*'    (1 reduction, or a shift)
    8 SR caused by freestore              with trailing * or &

state 778: IDENTIFIER '(' NEW INT '*' CONST  .  '&'    (1 reduction, or a shift)
    8 SR caused by freestore              with trailing * or &

state 779: IDENTIFIER '(' NEW INT '*'  .  '*'    (1 reduction, or a shift)
    8 SR caused by freestore              with trailing * or &

state 779: IDENTIFIER '(' NEW INT '*'  .  '&'    (1 reduction, or a shift)
    8 SR caused by freestore              with trailing * or &

state 1038: IDENTIFIER '{' TYPEDEFname '(' '(' TYPEDEFname  .  ')'    (1 reduction, or a shift)
    5 SR caused by redundant parened TYPEDEFname redeclaration vs old style cast
    Make declaration rather than expression.

state 1100: IDENTIFIER '{' IF '(' IDENTIFIER ')' ';'  .  ELSE    (1 reduction, or a shift)
    1 SR caused by dangling else and my laziness

state 1102: IDENTIFIER '{' TYPEDEFname '(' '(' TYPEDEFname '[' ']'  .  ')'    (1 reduction, or a shift)
    5 SR caused by redundant parened TYPEDEFname redeclaration vs old style cast
    Make declaration rather than expression.

state 1103: IDENTIFIER '{' TYPEDEFname '(' '*' '(' TYPEDEFname  .  ')'    (1 reduction, or a shift)
    5 SR caused by redundant parened TYPEDEFname redeclaration vs old style cast
    Make declaration rather than expression.

state 1105: STRUCT IDENTIFIER '{' TYPEDEFname '(' TYPEDEFname ')'  .  ';'    (2 reductions)
    6 RR caused by constructor declaration vs member declaration

state 1105: STRUCT IDENTIFIER '{' TYPEDEFname '(' TYPEDEFname ')'  .  '{'    (2 reductions)
    6 RR caused by constructor declaration vs member declaration

state 1152: STRUCT IDENTIFIER '{' TYPEDEFname '(' TYPEDEFname '[' ']' ')'  .  ';'    (2 reductions)
    6 RR caused by constructor declaration vs member declaration

state 1152: STRUCT IDENTIFIER '{' TYPEDEFname '(' TYPEDEFname '[' ']' ')'  .  '{'    (2 reductions)
    6 RR caused by constructor declaration vs member declaration

state 1175: STRUCT IDENTIFIER '{' EXTERN INT '(' TYPEDEFname '[' ']' ')'  .  ';'    (2 reductions)
    6 RR caused by constructor declaration vs member declaration

state 1175: STRUCT IDENTIFIER '{' EXTERN INT '(' TYPEDEFname '[' ']' ')'  .  '{'    (2 reductions)
    6 RR caused by constructor declaration vs member declaration